package ro;

import java.util.ArrayList;

public class Edge {

	int source;
	int weight;
	int target;
	
	public Edge(int source, int weight, int target) {
		this.source = source;
		this.weight = weight;
		this.target = target;
	}
	
	public String toString(){
		return "["+source +", "+weight+", "+target +"]";
	}
	
	
	public static void triRapide(ArrayList<Edge> edges, ArrayList<Boolean> bool)
    {
    triRapide(edges,0,edges.size()-1, bool);
    }



    public static void triRapide(ArrayList<Edge> edges)
    {
    triRapide(edges,0,edges.size()-1);
    }

	
    private static int partition(ArrayList<Edge> edges,int deb,int fin, ArrayList<Boolean> bool)
    {
    int compt=deb;
    int pivot=edges.get(deb).weight;
    for(int i=deb+1;i<=fin;i++)
        {
        if (edges.get(i).weight<pivot)
            {
            compt++;
            echanger(edges,compt,i, bool);
            }
        }
    echanger(edges,deb,compt, bool);
    return(compt);
    }

    private static int partition(ArrayList<Edge> edges,int deb,int fin)
    {
    int compt=deb;
    int pivot=edges.get(deb).weight;
    for(int i=deb+1;i<=fin;i++)
        {
        if (edges.get(i).weight<pivot)
            {
            compt++;
            echanger(edges,compt,i);
            }
        }
    echanger(edges,deb,compt);
    return(compt);
    }

    private static void echanger(ArrayList<Edge> edges, int i, int j, ArrayList<Boolean> bool) {
		Edge edgei= edges.get(i);
		Edge edgej = edges.get(j);
                Boolean b1 = bool.get(i);
                Boolean b2 = bool.get(j);
		edges.set(i, edgej);
		edges.set(j, edgei);
                bool.set(i, b2);
                bool.set(j, b1);
		
	}

     private static void echanger(ArrayList<Edge> edges, int i, int j) {
		Edge edgei= edges.get(i);
		Edge edgej = edges.get(j);
		edges.set(i, edgej);
		edges.set(j, edgei);

	}



	private static void triRapide(ArrayList<Edge> edges,int deb,int fin, ArrayList<Boolean> bool)
    {
    if(deb<fin)
        {
        int positionPivot=partition(edges,deb,fin, bool);
        triRapide(edges,deb,positionPivot-1, bool);
        triRapide(edges,positionPivot+1,fin, bool);
        }
    }

        private static void triRapide(ArrayList<Edge> edges,int deb,int fin)
    {
    if(deb<fin)
        {
        int positionPivot=partition(edges,deb,fin);
        triRapide(edges,deb,positionPivot-1);
        triRapide(edges,positionPivot+1,fin);
        }
    }

	
}
